-- comment out module line to load 
-- file directly.  Uncomment to allow
-- other files to "require" this one.  

module(..., package.seeall) 

gr = require "graphs" 
q = require "queues" 
st = require "stacks"

-- bfs traverses g breadth first starting from s.
-- It returns an array bfs_results.  
-- The entry for node n in bfs_results (if any) 
-- is a table 
--      { d = j, pi = m }
-- where j is the radius at which node n was found,
-- and pi is the predecessor from which it was found.  

-- Node n has no entry (that is, bfs_results[n] is NIL) 
-- if BFS from s never reaches node n.

-- Caution:  This means that when traversing the values 
-- in bfs_results later, you have to use 

--     for n,table in pairs(bfs_results) do ... 

-- and *not* ipairs().  ipairs will stop at the gaps that 
-- indicate unreached nodes.    


function bfs(g,s) 
   local bfs_results = {} 
   local bfs_q = q.new() 

   -- This local function says what to do at each step.

   local function step()
      local u = q.dequeue(bfs_q) 
      if u			-- will be nil when queue is done 
      then 
	 -- this for loop binds e in turn to each edge 
	 -- in the edge list for node u 
	 for _,e in pairs(g[u]) do 
	    local v =		-- get the dst 
	       e.dst		-- from the edge structure
	    -- is this node new?  
	    if not(bfs_results[v]) 
	    then 
	       bfs_results[v] = {d = (bfs_results[u].d)+1, 
				 pi = u}
	       -- queue up v so we can look 
	       -- for its neighbors later:  
	       q.enqueue(bfs_q,v) 
	    end
	 end
	 step()			-- keep stepping till queue empty  
      else 
	 return bfs_results 
      end
   end

   bfs_results[s] = {d = 0} 	-- s is the center, radius 0; no predecessor
   q.enqueue(bfs_q,s) 
   step() 			-- start stepping 
   return bfs_results
end

-- print procedure for bfs results data structure. 

function print_bfs_results(g,r) 
   local radius = 0 

   -- local function to print entries at radius i,
   -- return false if nothing is at this radius 

   local function at_radius(i) 
      local continue = false 
      io.write(string.format("\n\nAt radius     %d:   ", i))
      for n,t in pairs(r) do 
	 if t.d == i 
	 then 
	    continue = true 	-- something at this radius! 
	    io.write(string.format("\n  %s, from %s", 
				   gr.name_of_node(g,n),
				   (gr.name_of_node(g,t.pi) or "")))
	 end
      end 
      io.write(string.format("\n\n~~~~\n"))
      return continue
   end

   while at_radius(radius) do radius=radius+1 end
end 
   

-- factory function for time functions.
-- Every time it is called it allocates a 
-- location with contents 0, and returns a *function*.
-- That function, each time it is called, 
-- increments the location contents, 
-- then reports the contents as the current time.  

function timer() 
   local time = 0 
   return
   function () 
      time = time+1 
      return time 
   end
end 

function dfs(g) 
   local dfs_results = {} 
   local time = timer()  

   -- Fill this in to work by a recursive 
   -- function, without a stack data structure.  
   -- See below for the version with stack data structure.  

end

-- Do DFS on graph g, using a stack to maintain 
-- the discovered but not yet finished nodes.  
-- The results take the form of an array with an
-- entry for each node i.  The value at 
-- dfs_result[i] is a table of the form

--        { disc = t1, fin = t2, pi = j, neighbors_done = b}

-- where t1 is the time of discovery, 
--	 t2 is the time dfs finishes with node i, 
--	 pi is the predecessor meaning the node j
--	   from which i was discovered.  
--	 neighbors_done is a boolean.   b will be true
--	   at the end; it becomes true when dfs has handled
--	   the edges leading out from node i.

function dfs_stack(g) 
   local dfs_results = {} 
   local time = timer() 
   local s = st.new() 

   -- the fn push_new_neighbors goes through the 
   -- neighbors of i and pushes any new neighbors j, 
   -- as indicated by not yet having any dfs_results[j].  
   -- mark the current time and the predecessor i.  

   local function push_new_neighbors (i) 

      -- We can use ipairs since the edges array is gap-less. 

      for _,e in ipairs(g[i]) do 
	 local j = e.dst
	 if not(dfs_results[j])	-- New entry?
	 then 
	    dfs_results[j] = { disc = time(), pi = i } 
	    st.push(s,j)	-- Process its neighbors soon.  
	 end
      end
   end	 

   -- we walk through the nodes.  
   -- if we havent seen a node before, we push it
   -- and then as long as the stack is non-empty we
   -- push new neighbors 
   -- or else pop off nodes, marking them as finished 

   for i = 1,g.length do 
      if not(dfs_results[i])	-- is i a new node?  
      then 
	 dfs_results[i] = 
	    { disc = time() , 
	      pi = false }	     -- new, no predecessor pi 
	 st.push(s,i)		     -- process its neighbors next
	 while (not(st.empty(s))) do -- Run till stack empties.
	    local i = st.top(s)	     -- process top node 
	    local t = dfs_results[i] -- what we know about this guy
	    if t.neighbors_done 
	    then 
	       t.fin = time() 	-- finish this guy
	       st.pop(s)	-- pop him off the top  
	    else
	       push_new_neighbors(i) -- process neighbors for top guy 
	       t.neighbors_done = true -- but dont process neighbors again! 
	    end
	 end
      end
   end
   return dfs_results 
end

